Notes
Slide Show
Outline
1
Neuronske mreže








  • Student: Predrag Kostić
  • Br. indeksa: 10245
2
Rezime
  •      U ovom radu, opisan je jedan stručni savetodavni sistem za raspoređivanje rada u poštanskoj kompaniji (kompaniji za usluge raznošenja). Taj sistem dodaje interaktivne konverzaciono-grafičke osobine i potprogram kao podršku dispečeru u njegovim/njenim zadacima  i predlaže odgovarajuću odluku kada naiđe novi zahtev. Eksperiment sa profesionalnim dispečerom je takođe prikazan.
3
Deo 1: Uvod
  • Prevoz je jedna od suštinskih delatnosti unutar mnogih organizacija. Roba i usluge  se distribuiraju mušterijama preko službe prevoza, pa ova delatnost mora biti efikasno izvršena. U suštini, efikasnost utiče na smanjenje troškova operacija i povećanje kvaliteta usluge. Gledano sa strane dispečera, sposobnost da se nađe dobar kompromis između ova dva suprotna zahteva je veoma važno pitanje.


  • Brojni primeri distribuiranja u “realnom vremenu” mogu se naći u praksi, kao što su ambulantne ili policijske usluge, usluge slanja paketa ili kućne dostave, transport hendikepiranih, kao i mnoge druge. U ovom delu, mi smo se fokusirali na specifičnu oblast:  kompaniju za poštanske usluge iz Montreala. Ovde, pisma moraju biti sakupljena i dostavljena sa jednog mesta na drugo u uličnoj mreži, tako da zadovolji prioritete korisnika usluga. Za  prioritete su obično navedeni rokovi maksimalnog vremena preuzimanja i dostavljanja ( npr. pismo mora biti preuzeto za vreme od 30min, i dostavljeno u vremenu od 90min.).
4
Deo 1: Uvod
  • Da bi dosledno zadovoljio zahteve na najbolji mogući način uz pomoć omogućenog voznog parka, dispečer mora obratiti pažnju na mnogo različitih faktora, kao što su:


  • Trenutna pozicija svakog od vozača,
  • Planiran pravac kretanja i raspored svakog vozača (za prethodno dodeljen zahtev),
  • Lokacije za mesto preuzimanja i mesto dostave novog zahteva,
  • Distance i vreme putovanja između tačaka preuzimanja i dostave,
  • Karakteristike osnovne transportne mreže.


5
Deo 1: Uvod
  • Dakle, dispečer je ključni elemenat u kompanijama  za poštanske usluge. Nažalost, nije lako pronaći dobre dispečere, zbog specifičnih veština koje su neophodne za adekvatno izvršavanje zadatka. Štaviše, potrebno je dosta vremena za obuku dispečera, a njihova profesionalna karijera obično traje samo nekoliko godina zbog visokog nivoa napetosti usled potrebe za pravilnim reagovanjem, kao i zbog brzog i dinamičnog razvitka sredine.
  • Prema tome, razvoj stručnog sistema sposobnog za pomoć dispečerima vozila je od velike ekonomske važnosti. Međutim, naše sopstveno iskustvo je pokazalo da je to veoma teško, ako ne i nemoguće da se formalizuje znanje dispečera (npr. preko pravila odluke, semantičkih mreža itd.). Stoga, naš sistem je baziran na tehnikama učenja automata, na detaljnom učenju kroz primere, gde su primeri odluka sakupljeni i analizirani od strane sistema i prilagođeni kao proces dispečerovih odluka. Očigledno, mnogo je lakše uzeti primere odlučivanja dispečera nego izvući jasna pravila odlučivanja kod njih.
  • Potprogram učenja unutar sistema je baziran na modelu neuronskih mreža. Nakon faze obuke sa stručnjakom, sistem moze predlagati dispečeru vozače koji bi mogli zadovoljiti novopridošle zahteve. Naravno, dispečer ima konačnu odluku i slobodan je da prihvati ili odbije predloge sistema.
6
Deo 1: Uvod
  • Potprogram učenja je ugrađen u granicama konverzacije sa ciljem da pomaže dispečeru u njegovim zadacima. U ovom delu, razmatrani su sledeći problemi:
  • Lokalizacija novih zahteva unutar mreže ulica
  • Procena vremena putovanja i razdaljine
  • Rezultati dodele zahteva određenom vozaču
  • Definisanje kriterijuma učinka kod vozača, kao što su mogućnost zaobilaska, vreme preuzimanja, vreme dostavljanja itd.
  • Dinamika potprograma učenja
  • Za potrebe testa, prototip je korišćen kao simulator posebnih događaja, i primenjen je na prethodno sakupljena dokumenta i zahteve. Ovi podaci potiču iz poštanske kompanije iz Montreala.
  • U sledećem, drugom delu, upoznaćemo se sa problemima dodele. Zatim, deo 3 opisuje sistem dodele i njegove razne delove. Potprogram učenja je predstavljen u delu 4, i razni eksperimenti sa profesionalnim dispečerom opisani su u delu 5.
7
Deo 2: Problemi dodele
  • Posmatrajmo sledeći problem. Kompanija za poštanske usluge primila je poziv za preuzimanje i dostavu prioritetnog pisma u gradskom području. Svaki korisnik jasno definiše mesto preuzimanja i dostave, i maksimalno vreme usluge u svakoj od tačaka. Obzirom da većina korisnika traži brzu uslugu, putanja i raspored moraju biti određeni u realnom vremenu. U tako zahtevno osetljivom sistemu, sistem posmatra kada novi korisnik pozove kancelariju dispečera.U to vreme, pisma nekih ranijih korisnika su već dostavljena i, prema tome, više se ne razmatraju. Ostali korisnici su dodeljeni vozačima, i njihova pisma ili treba da budu preuzeta, ili su na putu da budu dostavljena. Pored toga,u to vreme, put i raspored za svakog vozača je poznat. Problem je odlučiti kom vozaču dodeliti zadatak, i koji put i raspored mu postaviti. U rešavanju ovog problema, dispečer mora pronaći kompromisno rešenje između dve stvari: umanjenja troškova i zadovoljenja potrebe korisnika.
  • Dinamički problemi kao što je ovaj i dalje su ostavljeni ljudima-dispečerima. Međutim, nekoliko algoritama je predloženo u literaturi, u pojedinim algoritmima na osnovu stečenog znanja koje su razvili Wilson i Covin ’79, za “dial-a-ride” transportni sistem u Ročesteru, NY. Dinamički programiran algoritam za pojedinačno vozilo je takođe, opisao Psaraftis ’80.
8
Deo 2: Problemi dodele
  • Ipak, pristup ovde pokazan je dosta drugačiji. Razvijen je sistem sposoban za simulaciju procesa odlučivanja dispečera eksperta, nakon faze obuke sa ovakvim ekspertom. Zato sistem može lako biti prilagođen drugim uslovima dodele. Pošto se procedura odlučivanja može dosta menjati od jedne organizacije do druge, nosivost sistema je veoma važan faktor ovde.


9
Deo 3: potprogram dodele
  • Sistem uključuje i potprogram dodele za asistiranje dispečeru pri njegovim zadacima, kao i potprogram učenja za predloge odluka. U ovom delu, mi ćemo se ograničiti na razne delove potprograma dodele. Potprogram učenja biće razmatran u sledećoj oblasti.
  • Slika 1 opisuje tok kontrole između 5 komponenti potprograma dodele. Ove komponente biće sada opisane redom.
10
3.1. Lokalizacija zahteva
  • Unutrašnji prikaz cele mreže ulica u Montrealu nalazi se u sistemu. Svaki čvor u ovoj mreži predstavlja raskrsnicu ulica a svaka veza je deo ulice između dve raskrsnice. Unutrašnji prikaz mreže uključuje
  • 20 000 čvorova, 30 000 veza i 6 000 ulica. Zadatak potprograma za lokalizaciju je da transformiše adresu preuzimanja i dostave u element na strukturi mreže (npr. Čvor ili vezu). Adresa može biti zadata na četiri jasno određena načina:
  • Građanskom adresom, imenovanjem, građanskim brojem i imenom ulice,
  • Poštanskim kodom,
  • Imenom (npr. Montrealski  Univerzitet),
  • Raskrsnicom ulica (npr. ugao ulice Saint-Laurent i Sherbrooke)
  • Kada je adresa locirana na mreži, njene koordinate su pronađene i razdaljina i vreme prenosa na drugu adresu mogu biti procenjene.
11
3.2. Procena razdaljine
  • Ovde je problem proceniti dužinu najkraćeg puta između dve adrese u mreži (nadalje, to će se odnositi na “tačnu razdaljinu”). Dva alternativna pristupa će biti razmatrana ovde:
  • Proračunavanje tačne razdaljine između svih parova adresa u mreži, i njihovo skladištenje u tabeli rastojanja za naredno korišćenje.
  • Proračunavanje tačne razdaljine između dve adrese svaki put kada je to potrebno.
  • Prvi pristup nije realan za velike mreže, iz razloga što bi tada tabela rastojanja bila prevelika da bi bila postavljena u glavnu memoriju ( primetimo da N adresa generišu O(N2) parovnih rastojanja). Sa druge strane izračunavanje tačne razdaljine “po zahtevu” je nefunkcionalno zbog mnogo vremena potrošenog na računanje. Procena najkraće putanje je skupa jer dve tačke mogu biti dosta udaljene, i specifične potrebe moraju biti uračunate pri proceni, kao što su jednosmerne ulice i zastoji pri skretanju u levo.
  • Kako bi dosledno omogućili kraće vreme izračunavanja, uzeli smo međupristup tako što smo podelili mrežu ulica na 502 zone veličine kvadratnog kilometra. Unutar svake zone, najvažnija raskrsnica je definisana kao “centar” zone. Tačne razdaljine su izračunate između svakog para centara, i postavljene su u tabelu rastojanja. Veličina tabele je oko 1MB, i može biti postavljena u glavnu memoriju
12
3.2. Procena razdaljine
  • Da bi odredili tačnu razdaljinu između lokacije 1 u zoni 1 i lokacije 2 u zoni 2 , korišćena je sledeća relacija:




  • Bez obzira na odnos između samih položaja, očekivano je da odnos između tačnog i Menhetn rastojanja između centra u zoni 1 i centra u zoni 2 bude približno jednak odnosu između tačnog i Menhetn rastojanja između lokacije 1 i lokacije 2. Obzirom da je razdaljina između centara u zoni 1 i zoni 2 poznata, i Menhetn razdaljina je laka za izračunavanje, mi imamo način za brzi proračun tačne razdaljine između lokacije 1 i lokacije 2. Detaljnije, ako postoji smetnja između 2 zone (npr. industrijsko postrojenje), odnos razdaljina između centara zone 1 i zone 2, biće veći i dovešće , preko odnosa, do veće procene između tačnog rastojanja između lokacije 1 i lokacije 2. Ovakav pristup se pokazao kao veoma brz i dosta precizan. U slučajevima kada su obe lokacije u istoj zoni, koristi se samo Menhetn rastojanje.
13
3.2. Procena razdaljine
  • Slika 2 pokazuje razliku između tačne i Menhetn razdaljine u uličnoj mreži. Sivi pravougaonici predstavljaju kuće ili blokove kuća, a beli delovi između sivih pravougaonika predstavljaju ulice u mreži. Kao što možemo videti u primeru, tačno rastojanje je veće od Menhetn rastojanja, jer pri tačnom računanju moraju se pratiti ulice u mreži, da bi se izbegle prepreke.
14
3.3. Procena vremena prenosa
  • Kada saznamo rastojanje između dve tačke, vreme prenosa možemo izvesti na osnovu prosečne brzine kretanja vozila. U sistemu, brzina je funkcija razdaljine. Zapazimo da kada su dve tačke dosta udaljene, vozač obično koristi veće ulice, i prosečna brzina se poveća.
  • Funkcija brzine uključuje šest parametara:
  • VITMIN, minimalnu brzinu,
  • VITMOY, prosečnu brzinu,
  • VITMAX, maksimalnu brzinu
  • d1,d2 i d3, tri tačke duž ose razdaljine za definisanje funkcije brzine.
  • Sa ovim parametrima, po delovima linearna funkcija brzine, kao što je prikazano na slici ispod, je definisana:
15
3.3. Procena vremena prenosa
  • Za zadato rastojanje d izmedju dve tačke, prosečna brzina je zatim brzo određena i vreme prenosa je procenjeno.
  • Dodatni parametri su takođe dostupni modelu kao spoljašni faktori koji deluju na prosečnu brzinu, kao što su:
  • Meteorološki uslovi. Vreme prenosa može biti pomnoženo  sa koeficijentom između 1 i 5 koji označavaju teža stanja na putevima ( jaku kišu, sneg),
  • Produktivnost vozača. Vreme prenosa može biti podeljeno koeficijentom između 1 i 2, u zavisnosti od vozača. Koeficijenat 1 je za normalnog, a koeficijenat 2 je za dva puta bržeg od normalnog.
  • Gužva u saobraćaju. Tokom špica, ima mnogo više gužve u saobraćaju. Vreme prenosa može biti pomnoženo koeficijentom od 1 do 2 da bi se uzeo u obzir i faktor gužve.
  • Na osnovu svega toga, vreme prenosa se može prikazati kao:
16
3.4. Ubacivanje novih zahteva
  • Zadatak dispečera je da dodeli novi zahtev nekom od raspoloživih vozača. Koristeći tehnike opisane u poglavljima 3.2. i 3.3. za procenu rastojanja i vremena prenosa, sistem može pomagati dispečeru pri oceni rezultata dodavanja novog zahteva u neku od postojećih trasa. Na osnovu ovih informacija, mnogo je lakše dispečeru da donese dobre odluke.
  • Očigledno, mnoge dodatne tačke su izvodljive u svakoj trasi, iz razloga što najveći deo vremena usluge određenog od strane korisnika nije teško prilagodljiv, već normalno predpostavljen. Jedini uslov je da tački dostave mora predhoditi tačka preuzimanja. Prema tome, usvojena ubačena tačka je odabrana u svakoj trasi tako da minimizuje obilaženje (u vremenu) plus dodatna kazna za naknadno zadržavanje uneto u trasu sa novim zahtevom. Naime, ako je tačka preuzimanja  +j zahteva j uneta između servisnih tačaka i i k, tačka dostavljanja –j zahteva j je ubačena između l i m, i       je vreme prenosa između i i j, troškovi dodavanja bi bili smanjeni na:
17
3.4. Ubacivanje novih zahteva
  • U ovoj formuli,                          predstavljaju novo vreme usluge, staro vreme usluge i maksimalno vreme usluge, respektivno. Prve dve komponente u formuli troškova predstavljaju zaobilazno vreme za nova mesta preuzimanja i dostave, dok je treći termin suma naknadnog kašnjenja preko +j,-j i svih ostalih servisnih tačaka koje nailaze posle +j u trasi (većina promenljivih od  +j  i  –j su postavljene na 0). Minimizacija obilaznog vremena je heuristicki način smanjenja sume poremećaja u trenutnoj trasi. Sa druge strane, jedna promena obilaznog vremena može izazvati mnogo zakasnelih usluga u jednoj trasi i nekoliko u drugim trasama, u zavisnosti od razlike između proračunatog i maksimalnog vremena usluge. Ovo je u obračunu uzeto kaozadnja stavka u formuli troškova.
  • Slika 4 ilustruje proces dodavanja. Na slici, +j i –j predstavljaju respektivno tačke preuzimanja i dostave zahteva j, a X predstavlja zadnju tačku usluge vozača u trenutnom vremenu. Dakle, vozač je već uslužio tačku X, i krenuo je prema tački preuzimanja zahteva 1. U to vreme, korisnik 3 poziva servis. Dodato mesto sa minimalnim troškovima za ovaj novi zahtev je pokazano na slici. Sa ovim novim zahtevom, planirana vremena usluge u +2, -2 i -1 su odložena, i ubačena nova vremena usluge u sistem.
18
3.4. Ubacivanje novih zahteva
19
3.5. Odabir vozača
  • Prezentacija različitih alternativnih trasa je omogućena da pomogne dispečeru da odabere odgovarajućeg vozača. Detaljnije, sistem ističe devet karakteristika ili osobina da bi opisao trasu:
  • D.E.  Zaobilazno vreme usled novog zahteva
  • P.T. Vreme preuzimanja novog zahteva
  • D.T. Vreme dostave novog zahteva
  • Avg. P Lat. Prosečno vreme kašnjenja na mesto preuzimanja usled obaveze zbog umetanja novog zahteva
  • Avg. D Lat. Prosečno vreme kašnjenja na mesto dostave usled obaveze zbog umetanja novog zahteva
  • #P Lat. Broj naknadnih zakasnelih usluga na mestima preuzimanja, usled obaveze zbog umetanja novog zahteva
  • #D Lat. Broj naknadnih zakasnelih usluga na mestima dostave, usled obaveze zbog umetanja novog zahteva
  • #Req. Broj zahteva na trasi
  • Et. Tr. Odnos praznog vremena prenosa i ukupnog vremena prenosa. Vozilo ide prazno kada se krece prema tački preuzimanja, i tada nema pošte u vozilu.
20
3.5. Odabir vozača
  • Ekran 1, koji vidimo na slici 5, rangira vozače ili trase prema visini karakteristika (primetimo da NN predstavlja produkt neuronskih mreža, kao što će biti opisano u sledećem delu). Ova slika prikazuje da je vozač Potvin najbolji vozač za usluživanje novih zahteva ako uzmemo u obzir zaobilazne karakteristike DE, sa vremenom obilaska od 2.1 min. Vozač Vincent je drugi sa vremenom zaobilaska od 3.3 min., itd. Mali prozori su klizni, pa je moguće videti mesto na rang listi bilo kog vozača u vezi sa bilo kojom karakteristikom.
21
3.5. Odabir vozača
  • Ekran 2, koji vidimo na slici 6, je alternativni ekran. On pokazuje rangiranje svih vozača odjednom. Na primer, vozač Rioux je peti prema vremenu obilaska DE, prvi po vremenu preuzimanja PT, prvi po vremenu dostave DT, itd. Da napomenemo da slike 5 i 6 predstavljaju prave ekrane.


22
3.5. Odabir vozača
  • Gledajući ove brojeve, dispečer može odabrati određenog vozača, klikćući mišem na liniju sa vozačevim imenom. Po selektovanju, prikazuje se cela trasa, sa specijalnim zasenčanjem za mesta preuzimanja i dostave novog zahteva.(videti sliku 7). Na trasi je prikazano planirano i maksimalno vreme usluge za obe adrese, kao i simbol “>” koji se pojavi između dve vrednosti kada se detektuje neko kašnjenje.
  • Dispečer mora potvrditi trasu. Ako mu se ne sviđa trasa, omogućene su mu tri mogućnosti. Prvo, on može pomeriti tačke preuzimanja i dostave na druge lokacije unutar trase, kako bi našao bolje mesto dodavanja. Kada su tačke pomerene na novu lokaciju, planirano vreme usluge u svakoj tački duž trase se automatski koriguje. Dispečer može zatražiti korekciju rang liste na ekranu 1 i ekranu 2, baziranu na novom mestu dodavanja.
  • Druga mogućnost je da poništi selekciju, i vrati se na ekrane 1 i 2 kako bi odabrao novog vozača. Kada dispečer potvrdi odabir vozača, trasa se trajno menja kako bi uključila novi zahtev.
  • Treća mogućnost je ostavljanje zahteva na listu “neodlučenih” zahteva, i sačekati druge zahteve da dođu pre konačne odlike.
23
3.5. Odabir vozača
24
Deo 4: potprogram učenja
  • Potprogram učenja ima za cilj predlaganje “dobrih” vozača za usluživanje novih zahteva. Bez ovog potprograma, sistem bi imao neaktivnu ulogu u pomaganju dispečeru. “Back propagation” neuronska mreža predstavlja srž potprograma učenja. (za totalni opis ovog modela pogledati [Rumelhart i McClelland 86]).
  • “Backpropagation” mreža je tipično sastavljena od tri sloja prostih procesorskih jedinica, nazvanih ulazni sloj, skriveni sloj i izlazni sloj. Svaki sloj je u potpunosti povezan sa sledećim slojem težinskim vezama. Ulazne vrednosti su prdviđene za ulazni sloj, i ove vrednosti se prostiru duž težinskih veza do skrivenog sloja gde se obrađuju. Nakon toga, ponavlja se isti postupak između skrivenog i izlaznog sloja. Konačne vrednosti smeštene su u izlaznom sloju, i odgovaraju poslednjoj karakteristici (ili izlazu) mreže.
  • Tokom prostiranja, skrivene i izlazne jedinice transformišu svoje ulaze putem dobro poznate sigmoidalne aktivacione funkcije [Rumelhart i McClelland 86]:
25
Deo 4: potprogram učenja
  • Ne vredi ništa ako je aktivaciona vrednost svake jedinice na intervalu [0,1] posle procesiranja ulaza od strane sigmoida. Praktično, aktivaciona vrednost izlaznih jedinica je vrednost izmedju 0 i 1, i ona je odgovor neuronske mreže na trenutni ulazni vektor.
  • Moć “backpropagation” mreža ogleda se u njihovim sposobnostima da se prilagode težini svojih veza kako bi naučili specifične zadatke. Algoritam učenja koristi željeni izlazni vektor ili odluke donete od strane eksperta za svaki ulazni vektor (opisujući problematičnu situaciju). Kada trenutni izlaz ne odgovara željenom izlazu, greška se koristi da prilagodi težinu veza između slojeva.
  • Mnogi parovi (ulaz,željeni izlaz) su određeni od strane mreže za svrhe vežbanja. Ovi parovi se obrađuju jedan po jedan od strane mreže da postepeno prilagode težine dok se ne pojavi konvergencija. Obično, beznačajno mala greška se podesi između trenutnog i željenog izlaza kako bi proverili ispravnost mreže, i vežba prestaje kada se pokazatelj ove greške stabilizuje.
  • Iz prethodnog obrazloženja, jasno je da podatak mora prvo biti kodiran u formu ulaznog vektora za neuronsku mrežu. U našem modelu, svaki ulazni vektor kodira opis situacije raspodele za svakog vozača pojedinačno. Ako je n broj vozača, n ulaznih vektora je prema tome kreirano za svaki novi zahtev. Ulazni vektor odabranog vozača je dobijen je na osnovu devet kriterijuma ili karakteristika opisanih u  delu 3.5 (zaobilazno vreme, vreme preuzimanja, vreme dostave, itd.).
26
Deo 4: potprogram učenja
  • Prema tome, ulazni vektor vozača  j za novi zahtev i je:



  • gde je       p-ta karakteristika vozača j za zahtev i , a m je broj karakteristika (u ovom slucaju m=9).
  • Veoma je važno da primetimo da svaka vrednost karakteristike       nosi mali značaj u sebi. Na primer, zaobilazno vreme od 15 min. za vozača može biti dobro ili loše, u zavisnosti od ostalih vozača. Prema tome, informacija je prosleđena za sve vozače. Ako mi želimo obezbediti “backpropagation” neuronsku mrežu sa opisom koji uključuje samo po jednog vozača u trenutku (po redu kako bi smanjilo veličinu ulaznih vektora), potrebneje da vrednosti karakteristika        budu transformisane u nove vrednosti koje mogu biti protumačene bez obraćanja pažnje na ostale vozače.
27
Deo 4: potprogram učenja
  • Mi tako prilagođavamo dve naredne transformacije kako bi postigli ovaj cilj:
  • Prevod. Zadati novi zahtev i i vrednost karakteristike        , sledeća transformacija je prva prilagođena:



  • gde je n broj vozača i m broj karakteristika. Za bilo koju karakteristiku p,            za najboljeg vozača j*, i preostale vrednosti                             odgovaraju razlici od najbolje vrednosti. Geometrički, ova transformacija prevodi ulazni vektor svakog vozača u odnosu na vektor
28
Deo 4: potprogram učenja
  • Normalizacija. Gornje vrednosti su normalizovane između 0 i 1, na sledeći način:
29
Deo 4: potprogram učenja
  •       Slika 8 pokazuje tri sloja neuronske mreže baziranih na kodiranju podataka za m=3 karakteristike. Za svaku normalizovanu vrednost karakteristike        postoji ulazna jedinica. Takođe postoje tri skrivene jedinice povezane sa svakom ulaznom jedinicom. Zadnji sloj sastoji se od jedinstvene izlazne jedinice        sa ciljem da uslovi višestruke procene kvaliteta vozača. Primetimo takođe da je ulazni sloj direktno povezan za skriveni sloj i za izlazni sloj. Direktna veza između ulaznih i izlaznih jedinica obično nije prisutna u standardnoj “backpropagation” mreži, ali bolji rezultati su zabeleženi sa ovim modelom.


30
Deo 4: potprogram učenja
  • Eksperiment opisan u poslednjem delu odnosi se na ovu mrežnu strukturu. Ipak, devet ulaznih jedinica je upotrebljeno, t.j. jedna ulazna jedinica za svaku vrednost karakteristike (pogledati deo 3.5)
  • Neuronska mreža je trenirana sa klasičnim “backpropagation” algoritmom [Rumelhart i McClelland 86]. Svaka odluka eksperta, koji je ili odabrao ili odbio vozača povezanog sa trenutnim ulaznim vektorom, iskorišćena je da poboljša tačnost mrežnog odgovora, i prilagodi težinu veza u slučaju greške. Kao što je pomenuto pre, greška je bazirana na razlici između odgovora mreže i željenog odabira. Ovde je željeni odabir postavljen na 1 za vozača odabranog od strane dispečera, a na 0 za drugačiji slučaj.
  • Kada je jednom uvežbana, neuronska mreža može biti prilagođena novim primerima: odgovor koji je blizu 1 znači da vozač koji je povezan sa trenutnim ulaznim vektorom je dosta pogodan za usluživanje novog zahteva, dok vrednost blizu 0 znači suprotno. Primetimo da se izlazi neuronske mreže pojavljuju na prozoru 1 unutar kliznog ekrana NN (videti sliku 5).
31
Deo 5: Simulator
  • Da bi sakupio primere odluka, potprogram dodeljivanja je sada ugrađen u poseban simulator događaja. Ceo sistem je sproveden u Turbo-Paskalu i pušten na IBM PS/2 mikroračunaru.
  • Dva tipa događaja se mogu javiti tokom simulacije: Događaj zahteva kada novi zahtev naiđe i događaj vozača kada se vozač javi sa mesta preuzimanja ili mesta dostave. Događaji zahteva se čitaju sa ulaznih dokumenata, a događaji vozača se generišu kada su zahtevi dodeljeni. Tokom simulacije, sat se pomerao u odvojenim vremenskim koracima zasnovanim na vremenski najbližem sledećem događaju. Kada je trenutni događaj  događaj zahteva, simulator se zaustavlja da bi dozvolio ekspertu da dodeli zahtev (videti deo 3).
32
Deo 5: Simulator
  • Ekran simulacije pokazan je na slici 9. Mali gornji prozor pokazuje trenutni događaj, koji je ili događaj zahteva ili događaj vozača (npr. događaj zahteva). Veliki prozor na sredini ekrana pokazuje trenutno stanje svih vozača. Ako je vozač slobodan, njegova trenutna pozicija je označena. U suprotnom, pokazane  su polazna i odredišna tačka vozača. Trenutno vreme usluge na polaznoj tački i očekivano vreme usluge na odredišnoj tački su takođe prikazani, kao i maksimalno vreme usluge u svakoj tački. Primetimo da je očekivano vreme usluge na odredišnoj tački uzeto od strane simulatora da bi odredilo sledeći događaj, vremenski najbliži. U trenutnom izvršavanju, očekivano i trenutno vreme usluge su isti, zato što simulator ne generiše još uvek neki neočekivani događaj (kao što su neočekivana kašnjenja, kvar na vozilima, itd.). Konačno, prozor pri dnu ekrana se koristi za nerešene zahteve.
33
Deo 5: Simulator
  • Sadašnji sistem dodeljivanja može biti iskorišćen na tri različita načina, kao što prikazuje slika 10.
  • Sakupljanje podataka. Ovde, odluke dispečera se sakupljaju tokom simulacije i skladište u dokument sa primerima vežbanja i testiranja da bi se kasnije iskoristili od strane neuronske mreže. Ovaj dokument sadrži vozače izabrane od strane dispečera za svaki zahtev, kao i opis situacije dodeljivanja za svakog vozača ( na osnovu karakteristika iz dela 3.5.).
  • Vežba/Testiranje neuronske mreže. Ovaj način korišćenja je uzet za treniranje ili testiranje neuronske mreže na osnovu dokumenta sa primerima kreiranog u “sakupljanju podataka”. U delu treniranja, primeri su iskorišććni da prilagode težine veza. U delu testiranja, karakteristike mreže se procenjuju poređenjem njenih odluka ( sa trenutnom grupom težina) sa odlukama dispečera. Kao što je prikazano na slici 10, ovaj deo uključuje samo potprogram učenja.
  • Predlog vozača. Ovde korisnik može pogledati predloge (prethodno uvežbane) neuronske mreže da bi dodelio novi dokument ili zahtev. Ako je tako poželjeno, težina veza neuronske mreže je prilagodjena kada se konačna odluka razlikuje od vrha rangiranih predloga neuronske mreže.
34
Deo 5: Simulator
35
Deo 6: Rezultati eksperimenta
  • Sa namerom da procenimo ispravnost potprograma učenja, izvršili smo eksperiment sa profesionalnim dispečerom na grupi zahteva prikupljenoj u radnom danu kompanije za poštanske usluge iz Montreala. Ukupno 140 zahteva je sakupljeno od 9.00h do 15.00h, i 12 vozača je bilo iskorišćeno za usluživanje ovih zahteva.
  • S’obzirom na kvalitet usluga, uzete su sledeće pretpostavke:
  • Maksimalno vreme preuzimanja zahteva j je postavljeno na vreme zahteva korisnika j plus 30 minuta (gde vreme zahteva korisnika j predstavlja vreme poziva)
  • Maksimalno vreme dostave zahteva j je postavljeno na vreme zahteva korisnika j plus 90 minuta.
  • Iz toga, kašnjenja na tačkama preuzimanja i dostave +j i –j su računata na sledeći način:
36
Deo 6: Rezultati eksperimenta
  • Prema tome, dispečer je podelio 140 zahteva redom na 12 vozača. Na kraju, 140*12=1680 ulaznih vektora je bilo omogućeno za uvežbavanje i testiranje neuronske mreže. Mi smo iskoristili 90 zahteva za uvežbavanje mreže i 50 zahteva za testiranje. Karakteristike mreže na grupi za testiranje su procenjene upoređivanjem, za svaki zahtev, rangiranja od strane neuronske mreže i vozača izabranog od strane dispečera. Ovo rangiranje je određeno sortiranjem izlaza neuronske mreže za sve vozače u opadajućem redu.
  • Na primer, pretpostavimo da su sortirani izlazi neuronske mreže za n=5 vozača:
  • Vozač 1:      0.9
  • Vozač 4:      0.8
  • Vozač 3:      0.6
  • Vozač 5:      0.4
  • Vozač 2:      0.1
  • Ako je izabran vozač 4 od strane dispečera, rangiranje dato od neuronske mreže za ovaj izbor je 2.
37
Deo 6: Rezultati eksperimenta
  • Ova rangiranja su prikazana u tabeli 1 za 50 zahteva u grupi za testiranje. Težine veza neuronske mreže se dobiju posle 100.000 težinskih korigovanja ili ponavljanja učenja na grupi zahteva za učenje (počinjuci sa slučajnim težinama). Učenje mreže na 486 IBM PS/2  trajalo je 24 sata.
38
Deo 6: Rezultati eksperimenta
  • Tabela 1 prikazuje da je 80% vozača odabrano od strane eksperta rangirano kao prvi, drugi ili treći od strane neuronske mreže (t.j. 40 odluka od 50). Štaviše, 94% vozača je rangirano kao prvi, drugi, treći ili četvrti od strane neuronske mreže. Ove cifre pokazuju da neuronska mreža može biti veoma korisna da odstrani vozače, i usmeri pažnju dispečera na najinteresantnije mogućnosti.
  • Nebitno je da li je dosta podjednako dobrih (podjednako loših) mogućnosti omogućeno ako se ne podudaraju izbori neuronske mreže i eksperta. U ovakvim situacijama, mreža uvek odabere prihvatljivog vozaća (t.j. nema “budalastih” izbora).
39
Deo 6: Rezultati eksperimenta
  • Takođe smo iskoristili naučenu mrežu da dodeljuje celu grupu zahteva jedan po jedan. Tada smo upoređivali trase neuronske mreže i trase dispečera, prema sledećim merama učinka:
  • Produktivnost. Mera produktivnosti upoređuje ukupno vreme putovanja na trasi sa sumom direktnih vremena putovanja između tačaka preuzimanja i dostave za svaki zahtev na trasi. Kasniji slučajevi odgovaraju situaciji kada je svaki zahtev uslužen od strane posebnog vozila (kao taxi služba).
  • U formuli ispod, produktivnost trase r je definisana kao odnos ove dve vrednosti. Primetimo da je u brojiocu suma direktnih vremena putovanja svih zahteva u u trasi.





  • Odnos praznog vremena putovanja i ukupnog vremena putovanja
  • Suma kašnjenja na mestima preuzimanja (u minutima)
  • Suma kašnjenja na mestima dostave (u minutima)
40
Deo 6: Rezultati eksperimenta
  • Kriva ispod pokazuje razvoj ovih vrednosti sa dodelom zahteva od strane mreže ili od strane eksperta. X-osa predstavlja broj odluka dodele, a Y-osa mere učinka pod analizom. Vrednosti su snimane posle svake sekvence od deset odluka i sabrane su. Na primer, mera produktivnosti kod 30-e odluke dodele je prosek uzet od svih trasa, posle dodavanja 30-og zahteva. U ovom procesu, svi dodeljeni zahtevi doprinose proseku.
  • Na svakoj slici, krive neuronske mreže su one sa malim krugovima, a krive dispečera su one sa malim kvadratićima. Kao što možemo videti, neuronska mreža pokazala se dobro u odnosu na prazno vreme putovanja, produktivnost, i kašnjenja na mesta preuzimanja. Ipak, ekspert je bolji u odnosu na kašnjenja na mesta dostave. Najčešće, trase neuronske mreže imaju dve zakasnele usluge na mestima preuzimanja (oko 5 minuta u svakom mestu), i tri zakasnele usluge na mestima dostave (oko deset minuta nu svakom mestu). Sa druge strane, trase dispečera imaju tri zakasnele usluge na mestima preuzimanja, i samo jednu zakasnelu uslugu na mestima dostave.
  • Prema tome, neuronska mreža se pokazala dosta dobro prema merama učinka. Čak iako se nije pokazala kao dispečer u odnosu na ukupna kašnjenja na mestima dostave, vrednosti neuronske mreže su veoma impresivne. Takođe, dispečer je pritisnut zbog važnosti dolaska u pravo vreme na mesto preuzimanja (korisnici ne vole da vide pismo na svome stolu dugo vremena po pozivu postanske kompanije!). Interesantno je da je neuronska mreža uradila veoma dobar posao u tom pogledu.
41
Deo 6: Rezultati eksperimenta
42
Deo 7: Zaključak
  • Sistem predstavljen u ovom radu je razvijen da predstavi upotrebljivost tehnologije neuronskih mreža u zadacima dodele vozila. Međutim, sistemu su potrebne dodatne osobine kako bi bio koristan u realnom ambijentu. Na primer, trenutna pozicija svakog vozača treba biti lakše korigovana (idealno bi bilo preko ‘on-board’ kompjutera), i revizija trasa trebala bi biti omogućena u slučajevima dugog neočekivanog kašnjenja.
  • U odnosu na potprogram učenja, faza vežbanja uzima dosta vremena, ali to nije toliko bitno, zato što to može biti urađeno sa unapred sakupljenim primerima odluka (kao što smo mi uradili u našim eksperimentima). Kada se nauči, mreža reaguje veoma brzo, i može biti upotrebljena u realnoj sredini.
  • Konačno, ne vredi ništa ako potprogram učenja uradi dobro, ako nije u saglasnosti sa  procenjenim vremenom putovanja i razdaljinama. Dispečer je uvideo da su vremena putovanja veoma realna u većini slučajeva, ali je očigledno da ove procene predstavljaju dodatni hendikep za potprogram učenja.